A computer network typically comprises a collection of interconnected nodes such as computer systems and switches, which may, in turn, be connected through an irregular configuration of transmission lines, i.e., links. The switches are specialized computers used to connect two or more links. Data is exchanged among nodes of such an "arbitrary-topology" network by passing packets from switch to switch over the links. Specifically, when a packet arrives on an incoming link, the switch decides onto which of the outgoing links that packet will be forwarded.
In a connection-oriented network a virtual circuit is commonly established when exchanging packets between nodes of the network. The virtual circuit is a temporary logical path connection that requires a set up procedure to "open" the virtual circuit prior to transferring the data packets and a release procedure to "close" the circuit once the data transfer is complete. This obviates the need for effecting routing decisions for each data packet that is transferred between the nodes once the circuit is opened.
For point-to-point communication, the set up procedure creates a virtual circuit by allocating certain switches and links in the network to establish the "best" route, according to conventional route configuration techniques, between a source node and a destination node. To illustrate, refer to FIG. 1A. Here, node A of network 10 performs a set up procedure to open a virtual circuit route that encompasses the switches S.sub.A-D. This route is identified by a virtual circuit (VC) number, VC2, that is associated with node A's local switch S.sub.A. In order to ensure that data packets subsequently transferred from node A always follow this virtual circuit route to node D, each switch along VC2 maintains a forwarding table with entries indicating where to forward the data packets in accordance with tile routing configuration results.
FIG. 1B illustrates tile forwarding tables 20a-d contained within the switches S.sub.A-D of the network 10. Each entry of the tables includes an incoming portion and an outgoing portion, with each portion including a port name and a VC number associated with that port. Each data packet transferred over the network contains a VC field identifying the open VC number on which it has arrived. Thus, when a packet is received at an incoming port of switch S.sub.c, that switch searches the left (incoming) portion 22i of its table 20c, using the incoming port, e.g., Z, and VC number found in the packet, e.g., VC7, as the key. When a match is found, the outgoing portion 22o of tile entry identifies the VC number, e.g., VC4, to insert into the VC field of the packet and the port, e.g., Q, to which it should pass the packet. It is therefore apparent that the VC numbers and forwarding tables provide enough information to guide tile data packets through the allocated switches and links to the destination.
Multicasting involves transmitting a single multicast packet from a source node and having it received by a group of destination nodes. A problem associated with this type of point-to-multipoint communication technique concerns forming an efficient "delivery tree", i.e., a collection of nodes and links, that the multicast packet must traverse to reach the destination nodes. One approach, known as Core Based Trees (CBT), addresses this problem by establishing a core, point-to-point virtual circuit "tree" and then executing a set up procedure for each additional destination node of the group. However, the CBT approach is "static", in the sense that if a more efficient path exists, the delivery tree cannot easily be adapted to the "better" topology.
Another problem involves adding and deleting nodes from tile multicast group of destinations. In CBT networks, each destination node initiates a procedure to add or delete itself; accordingly, the source node is unaware of the tree configuration and its constituent destination nodes.
An alternative to tile CBT technique involves creating subsequent "branch" links for the additional destination nodes without destroying the existing tree connections. Such an approach is illustrated in FIG. 2. Here, a tree is formed that consists of virtual circuits from source node N to a multicast group of destination nodes D1 and D2; specifically the virtual circuit to node D1 encompasses switches S.sub.A and S.sub.F, and the virtual circuit to node D2 encompasses switches S.sub.A-D.
A branch link represented by VC8 is subsequently formed with the tree to add node D3 to tile group of destination nodes. However, the addition of VC8, in turn, forms a "loop" among the switches S.sub.A, S.sub.B, S.sub.C and S.sub.F and the intervening links, thereby creating an unstable topology. Specifically, if tile tree connections are bidirectional, i.e, packets may flow through the ports of switches S.sub.A and S.sub.C in both directions as indicated by the double-headed arrows 22, a packet that is propagating within the loop may revolve endlessly around that loop, thereby adversely affecting the bandwidth of the network. If the connections are unidirectional as indicated by the single-headed arrows 21 flowing into switch S.sub.E, duplicate copies of the packets may be delivered to the destination node D3 which again, negatively affect bandwidth.
Another known point-to-multipoint communication technique requires each destination node to "register" with its local switch to receive packets addressed to a particular multicast address. Specifically, the destination node sends a request to its local switch which then forwards the request to all the switches in the network. Each switch in the network updates its forwarding table to store routing information, i.e., state, pertaining to all of the destination nodes for each multicast address. A disadvantage of this technique is that a significant amount of processing and storage overhead is needed for each switch to maintain state for each destination node.
Point-to-multipoint communication in a connectionless network involves transmitting a single multicast packet that is received by multiple destinations. For this type of network, however, each multicast packet contains a list of destination nodes. When the packet arrives at an incoming link of a first switch, that switch checks the list to select a set of outgoing links that will provide the best route to at least one of the destinations. The switch generates a new copy of the multicast packet for each selected outgoing link and includes, in each packet, those destinations that use the link. Ultimately, each multicast packet will identify only one destination and is treated as a normal data packet.
Therefore, it is among the objects of the invention to provide a method and apparatus for creating multicast virtual circuits in an arbitrary-topology network without disrupting the operation of the network.
Another object of the invention is to provide a method and apparatus for adding nodes to established multicast virtual circuits without affecting the performance of the network.
Another object of the invention is to provide a method and apparatus for easily modifying established multicast virtual circuits to reflect a more efficient topology.
Yet another object of the invention is to provide a mechanism for establishing multicast virtual circuits that incorporates features of a connection-oriented and a connectionless network.